『Discrete Mathematics and Its Applications』目次
About the author 著者について vi
Preface 序文 vii
Online Resources オンラインリソース xvi
To the Students 学生へのメッセージ xix
1 The Foundations:Logic and Proofs 基礎：論理と証明 1
1.1 Propositional Logic. 命題論理 1
1.2 Applications Of Propositional Logic. 命題論理の応用 17
1.3 Propositional Equivalences. 命題の等価性 26
1.4 Predicates and Quantifiers. 述語と量化 40
1.5 Nested Quantifiers. 入れ子になった量化子 60
1.6 Rules of Inference.. 推論規則 73
1.7 Introduction to Proofs. 証明の導入 84
1.8 Proof Methods and Strategy. 証明の方法と戦略 115
2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices 基本的構造：集合、関数、数列、総和、行列 121
2.1 Sets. 集合 121
2.2 Set Operations. 集合の演算 121
2.3 Functions. 関数 133
2.4 Sequences and Summations. 数列と総和 147
2.5 Cardinality of Sets. 集合の濃度（カーディナリティ） 165
2.6 Matrices. 行列 179
End-of-Chapter Material 章末問題 188
3 Algorithms アルゴリズム 195
3.1 Algorithms アルゴリズム 201
3.2 The Growth of Functions 関数の成長 201
3.3 Complexity Of Algorithms アルゴリズムの複雑さ 216
End-of-Chapter Material 章末問題 231
4 Number Theory and Cryptography 数論と暗号理論 251
4.1 Divisibility and Modular Arithmetic 整除性と合同算術 251
4.2 Integer Representations and Algorithms 整数の表現とアルゴリズム 260
4.3 Primes and Greatest Common Divisors 素数と最大公約数 271
4.4 Solving Congruences. 合同式の解法 290
4.5 Applications Of Congruences 合同式の応用 303
4.6 Cryptography 暗号理論 310
End-of-Chapter Material 章末問題 324
5 Induction Recursion 帰納法と再帰 331
5.1 Mathematical Induction 数学的帰納法 331
5.2 Strong Induction and Well-Ordering 強い帰納法と整列順序 354
5.3 Recursive Definitions and Structural Induction 再帰的定義と構造的帰納法 365
5.4 Recursive Algorithms 再帰的アルゴリズム 381
5.5 Program Correctness プログラムの正当性 393
End-of-Chapter Material 章末問題 398
6 Counting 組合せ論（カウント） 405
6.1 The Basics of Counting カウントの基本 405
6.2 The Pigeonhole Principle 鳩の巣原理 420
6.3 Permutations and Combinations 順列と組合せ 428
6.4 Binomial Coefficients and Identities 二項係数と恒等式 437
6.5 Generalized Permutations and Combinations 一般化された順列と組合せ 445
6.6 Generating Permutations and Combinations 順列と組合せの生成 457
End-of-Chapter Material 章末問題 461
7 Discrete Probability 離散確率 469
7.1 An Introductionto Discrete Probability 離散確率の導入 469
7.2 Probability Theory 確率論 477
7.3 Bayes'Theorem ベイズの定理 494
7.4 Expected Value and Variance 期待値と分散 503
End-of-Chapter Material 章末問題 520
8 Advanced Counting Techniques 高度なカウント技法 527
8.1 Applications of Recurrence Relations 漸化式の応用 527
8.2 Solving Linear Recurrence Relations 線形漸化式の解法 540
8.3 Divide-and-Conquer Algorithms and Recurrence Relations 分割統治法と漸化式 553
8.4 Generating Functions 生成関数 563
8.5 Inclusion—lixclusion 包除原理 579
8.6 Applications Of Inclusion—ExcIusion 包除原理の応用 585
End-of-Chapter Material 章末問題 592
9 Relations 関係 599
9.1 Relations and Their Properties 関係とその性質 599
9.2 n-ary Relations and Their Applications n項関係とその応用 611
9.3 Representing Relations 関係の表現 621
9.4 Closures of Relations 関係の閉包 628
9.5 Equivalence Relations 同値関係 638
9.6 Partial Orderings 順序関係（半順序） 650
End-of-Chapter Material 章末問題 665
10 Graphs グラフ 673
10.1 Graphs and Graph Models グラフとグラフモデル 673
10.2 Graph Terminology and Special Types of Graphs グラフの用語と特別な種類のグラフ 685
10.3 Representing Graphs and Graph Isomorphism グラフの表現とグラフ同型 703
10.4 Connectivity 連結性 714
10.5 Euler and Hamilton Paths オイラー路とハミルトン路 728
10.6 Shortest-Path Problems 最短経路問題 743
10.7 Planar Graphs 平面グラフ 753
10.8 Graph Coloring グラフ彩色 762
End-of-Chapter Material 章末問題 771
11 Trees 木（ツリー） 781
11.1 Introductionto Trees 木の導入 781
11.2 Applications Of Trees 木の応用 793
11.3 Tree Traversal 木の走査 808
11.4 Spanning Trees スパニングツリー 821
11.5 Minimum Spanning Trees 最小全域木 835
End-of-Chapter Material 章末問題 841
12 Boolean Algebra ブール代数 847
12.1 Boolean Functions ブール関数 847
12.2 Representing Boolean Functions ブール関数の表現 855
12.3 Logic Gates 論理ゲート 858
12.4 Minimization of Circuits 回路の最小化 864
End-of-Chapter Material 章末問題 879
13 Modeling Computation 計算のモデル化 885
13.1 Languages and Grammars 言語と文法 885
13.2 Finite-State Machineswith Output 出力付き有限状態機械 897
13.3 Finite-State Machineswith No Output 出力なし有限状態機械 904
13.4 Language Recognition 言語の認識 917
13.5 Turing Machines チューリング機械 927
End-of-Chapter Material 章末問題 938
Appendices 付録 A-1
1 Axiomsforthe Real Numbers and the Positive Integers 実数および正の整数の公理 A-1
2 Exponential and Logarithmic Functions 指数関数と対数関数 A-7
3 Pseudocode 疑似コード A-11
メモ
$ cat work-convert.txt | awk -F'\t' '{ print "\t" $1 " " $2 "\n\t\t" $3 "\n\t\t" $4 }' > work-convert_2.txt
$ cat work-convert.txt | awk -F'\t' '{ print "\t" $1 "\t" $2 "\t" $3 "\t" $4 }' > work-convert_2.txt